package com.demo.jzoffer2;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

/**
 * @author gy
 * @date 2023/01/12
 */
public class Test0201_01 {
    /**
     * 输入一个字符串，打印出该字符串中字符的所有排列。
     *
     * 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
     *
     * 示例:
     *
     * 输入：s = "abc"
     * 输出：["abc","acb","bac","bca","cab","cba"]
     *
     * 限制：
     *
     * 1 <= s 的长度 <= 8
     * @param s
     * @return
     */
    List<String> res = new LinkedList<>();
    char[] c;

    public String[] permutation(String s) {
        c = s.toCharArray();
        dfs(0);
        return res.toArray(new String[res.size()]);
    }

    void dfs(int x){
        if (x == c.length-1){
            res.add(String.valueOf(c)); // 添加排列方案
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for (int i = x; i < c.length; i++) {
            if (set.contains(c[i])){
                continue; // 重复，因此剪枝
            }
            set.add(c[i]);
            swap(i,x); // 交换，将c[i] 固定在x位
            dfs(x + 1); // 开启固定 x + 1 位字符
            swap(i,x); // 恢复交换
        }

    }
    void swap(int a, int b) {
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;
    }

    @Test
    public void m1() {
        System.out.println(Arrays.toString(this.permutation("abc")));
    }

    @Test
    public void m2() {

    }

}
